package com.ljy.my_study.leetcode.medium.从前序与中序遍历序列构造二叉树;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.*;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @author: James
 * @create: 2022-04-03 20:53
 */
public class TestMain {

//    给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
//
//             
//
//    示例 1:
//
//
//    输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//    输出: [3,9,20,null,null,15,7]
//    示例 2:
//
//    输入: preorder = [-1], inorder = [-1]
//    输出: [-1]
//             
//
//    提示:
//
//            1 <= preorder.length <= 3000
//    inorder.length == preorder.length
//-3000 <= preorder[i], inorder[i] <= 3000
//    preorder 和 inorder 均 无重复 元素
//    inorder 均出现在 preorder
//    preorder 保证 为二叉树的前序遍历序列
//    inorder 保证 为二叉树的中序遍历序列
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {

    }

    Map<Integer,Integer> indexMap=new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len=inorder.length;
        for(int i=0;i<len;i++){
            indexMap.put(inorder[i],i);
        }
        return doBuildTree(preorder,inorder,0,len-1,0,len-1);
    }

    private TreeNode doBuildTree(int[] preorder,int[] inorder,int preorderLeft,int preorderRight,
                                 int indexorderLeft,int indexorderRight){
        if(preorderLeft>preorderRight){
            return null;
        }
        int preorderIndex=preorderLeft;
        int root=preorder[preorderIndex];
        int inorderIndex=indexMap.get(root);
//        左子树节点数量
        int preorderLeftSize=inorderIndex-indexorderLeft;
        TreeNode node=new TreeNode(root);
        node.left=doBuildTree(preorder,inorder,preorderIndex+1,preorderIndex+preorderLeftSize,
                indexorderLeft,inorderIndex-1);
        node.right=doBuildTree(preorder,inorder,preorderIndex+preorderLeftSize+1,preorderRight,
                inorderIndex+1,indexorderRight);
        return node;
    }
}
